package 二叉树遍历非递归实现;

import java.util.Stack;

/**
 * @author 冷加宝
 * @version 1.0
 */
//不用递归，用迭代的方式实现二叉树的三序遍历
public class BinaryTreeTraversalIteration {
    public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    //先序打印所有节点，非递归版
    public static void preOrder(TreeNode head){
        if(head == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while(!stack.isEmpty()){
            head = stack.pop();
            System.out.println(head.val + " ");
            if(head.right != null){
                stack.push(head.right);
            }
            if(head.left != null){
                stack.push(head.left);
            }
        }
        System.out.println();
    }

    //中序打印所有节点，非递归版
    // (对于一个节点，1.先处理其左边节点(有就全部入栈)，2.再处理自己，3.再处理右边节点(按步骤一进行处理)，)
    public static void inOrder(TreeNode head){
        if(head != null){
            Stack<TreeNode> stack = new Stack<>();
            while(!stack.isEmpty() || head != null){
                if(head != null){
                    stack.push(head);
                    head = head.left;
                }else{
                    head = stack.pop();
                    System.out.println(head.val + " ");
                    head = head.right;
                }
            }
            System.out.println();
        }
    }

    //后续打印所有节点，非递归版，使用两个栈
    //先序：中左右，则先序'：中右左，每次该弹出的时候，用另一个栈压入，则再次弹出就是：左右中
    public static void posOrderTwoStacks(TreeNode head){
        if(head != null){
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> collect = new Stack<>();
            stack.push(head);
            while(!stack.isEmpty()){
                head = stack.pop();
                collect.push(head);
                if(head.left != null){
                    stack.push(head.left);
                }
                if(head.right != null){
                    stack.push(head.right);
                }
            }
            while(!collect.isEmpty()){
                System.out.println(collect.pop().val + " ");
            }
            System.out.println();
        }
    }

    public static void posOrderOneStack(TreeNode h){
        if(h != null){
            Stack<TreeNode> stack = new Stack<>();
            stack.push(h);
        //    如果始终没有打印过节点，head就一直是头节点
        //    一旦打印过节点，h就变成打印节点
        //    之后h的含义：上一次打印的节点
            while(!stack.isEmpty()){
                TreeNode cur = stack.peek();
                if(cur.left != null && h != cur.left && h != cur.right){
                    //有左树且左树没处理过
                    stack.push(cur.left);
                }else if(cur.right != null && h != cur.right){
                    //有右树且右树没处理过
                    stack.push(cur.right);
                }else{
                    //左树，右树 没有 或者 都处理过了
                    System.out.print(cur.val + " ");
                    h = stack.pop();
                }
            }
            System.out.println();
        }
    }
}
